/*
提交链接：https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/submissions/572338377
902. 最大为 N 的数字组合-困难
完成日期：2024/10/13
数位DP
*/

class Solution {
public:
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        string s=to_string(n);
        int s_len=s.size(),d_len=digits.size();//s_len表示目标数字的位数，d_len表示给定可选数字的个数。
        int ans=0;
        for(int i=1;i<s_len;i++) ans+=int(pow(d_len,i));
        unordered_set<char> se;
        for(int i=0;i<d_len;i++)se.insert(digits[i][0]);//将全部数字放到一个集合中，记录一下digits数组都有哪些数字
        for(int i=0;i<s_len;i++){
            int tmp=0;
            for(int j=0;j<d_len;j++){
                if(digits[j][0]<s[i])tmp++;
            }
            if(tmp!=0)ans= ans + tmp*int(pow(d_len,s_len-i-1));
            if(se.find(s[i])!=se.end()){
                if(i==s_len-1)ans+=1;//digits数组存在与目标数字相等的组合
                continue;
            }
            else break;
        }
        return ans;
    }
};